A data storage system is typically able to service “data write” or “data read” requests issued by a host computer. A host may be connected to the storage system's external controller, or interfaces (IF), through various channels that transfer both data and control information (i.e. control signals). Physical non-volatile media in which data may be permanently or semi-permanently stored includes arrays of disk devices, magnetic or optical, which are relatively less expensive than semiconductor based volatile memory (e.g. Random Access Memory) but are relatively much slower in being accessed.
A cache memory is a high-speed buffer located between an IF and the disk device(s), which is meant to reduce the overall latency of Input/Output activity between the storage system and a host accessing data on the storage system. Whenever a host requests data stored in a memory system, the request may be served with significantly lower latency if the requested data is already found in cache, since this data must not be brought from the disks. As of the year 2004, speeds of IO transactions involving disk activity are typically on the order of 5-10 milliseconds, whereas IO speeds involving cache (e.g. RAM memory) access are on the order of several nanoseconds.
The relatively high latency associated with disk activity derives from the mechanical nature of the disk devices. In order to retrieve requested data from a disk based device, a disk controller must first cause a disk reading arm to physically move to a track containing the requested data. Once the head of the arm has been placed at the beginning of a track containing the data, the time required to read the accessed data on the relevant track is relatively very short, on the order of several microseconds.
One criterion or parameter which is often used to measure the efficiency of a cache memory system or implementation is a criterion referred to as a hit ratio. A hit ratio of a specific implementation is the percentage of “data read” requests issued by the host that are already found in cache and that consequently did not require time intensive retrieval from disk operations. An ideal cache system would be one reaching a 100% hit ratio. One way known in the art to improve performance by means of enhancing the hit ratio, includes implementing intelligent algorithms that attempt to guess in advance which portions of data stored on a disk device will soon be requested by a host. Once it has been estimated/guessed that some specific data will soon be requested, in anticipation of the request, the algorithm(s) “pre-fetch” the data into the cache, prior to actually receiving a request for the data.
Prefetch algorithms known in the art commonly fall into one of two categories. The first category or group includes algorithms which are based on the identification of sequential streams of read requests. If the storage system, or the cache controller therein, is able to identify that the host is issuing such sequential streams it may then assume that this kind of activity will be maintained for some time, and accordingly, it will guess which additional portions of data will be requested by the host in the near future. The anticipated portions are thus sent to the cache in advance. U.S. Pat. No. 5,682,500 to Vishlitzky, et al. describes such a prefetch method.
A second group of prefetch algorithms includes algorithms which are based on the identification of “hot zones” in the storage system. That is, a statistical analysis of activity in the system may indicate that a certain area, defined in advance as a potential “hot zone”, is being intensely addressed by a host, and consequently, a mechanism may be triggered to bring into cache all the data contained in that hot zone. The underlying assumption is that such data portions tend to be addressed in their totality, or in their majority, whenever they are addressed over a certain threshold of focused activity.
Unfortunately, the current approaches to prefetch algorithms require the use of considerable computational resources in order to (1) monitor activity on an ongoing basis, (2) decide on which data to prefetch, and (3) to implement the desired prefetch policy in a coordinated manner across the system. The amount of computational overhead involved in such activity may be considerable and costly, both in time, energy and hardware.
Beyond attaining high “hit ratios”, it is desirable for a cache to have additional properties, such as: scalability, the ability to maintain redundant caches and/or disks, and relatively few overhead management transactions associated with data processing.
There is a need for a method of implementing prefetch operations requiring a relatively small amount of computational and resource overhead, and for a system and circuit for implementing same.
There is a further need for a method of implementing prefetch operations requiring a relatively small amount of overhead and producing a relatively high cache hit ratio, and for system and circuit for implementing same.